package com.fantsey.test.juejin;

import java.util.ArrayList;
import java.util.List;

/**
 * 2 徒步旅行中的补给问题
 * @author fx
 * @date 2024/12/24
 * @since 1.0
 */
public class Question2 {
    /*输入：n = 5 ,k = 2 ,data = [1, 2, 3, 3, 2]
    2*1 + 1*2 + 1*3 + 1*2 = 9
    输出：9

    样例2：
    输入：n = 6 ,k = 3 ,data = [4, 1, 5, 2, 1, 3]
    1*4 + 3*1 + 0*5 + 0*2 + 2*1 + 0*3 = 9
    输出：9

     输入：n = 6 ,k = 4  ,data = [4, 5, 6, 2, 1, 3]
    4*3 + 2*1 + 1*2 = 14

    输入：n = 6 ,k = 4  ,data = [4, 3, 6, 2, 1, 3]

    [2,3,4,1]

    data = [4, 6, 3, 2, 1, 3]
    4*2 + 3*1 + 2*1 + 1*2 = 13

    样例3：
    输入：n = 4 ,k = 1 ,data = [3, 2, 4, 1]
    3 + 2 + +4+1 = 10
    输出：10*/
    public static void main(String[] args) {
//        int[] data = new int[]{1, 2, 3, 3, 2};
//        int n = 5;
//        int k = 2;
//        System.out.println(getMinCost(n, k, data));
//
//        int[] data2 = {4, 1, 5, 2, 1, 3};
//        int n2 = 6;
//        int k2 = 3;
//        System.out.println(getMinCost(n2, k2, data2));

        //int[] data3 = {7,25,20,  16（不大不小）,18（5）,7,20,15（8）,9,3（10）,12,  3,21,3,6（15）, 1,7,11,19,1（20）,2};
        //8*7 + 0*25 + 0*20 + 0*16 + 0*18 + 1*7 + 0*20+ 0*15 + 0*9 + 2*3 （10） + 0*12  + 0*3 + 0*21 + 0*3 + 0*6 + 6*1 + + 0*7+0*11+0*19+0*1+0*2= 87
        // 16 不大不小， 下一个比它的位置：2  当前剩余食物：5，可购买：8-5=3， 如果5>2, 则不够买
        // 18 不大不小， 下一个比它的位置：1  当前剩余食物：4，可购买：8-3=5， 如果4>1, 则不够买
        // 7 【7,20,15,9,3,12,3,21】，当前天数6， 下一个比它的位置：4  当前剩余食物：3，可购买：8-3=5， 3<4, 则需要购买4-3=1

        //8+1+6+

        /*int[] data3 = {7,25,20,16,18,7,20,15,9,3, 12,3,21,3,6, 1,7,11,19,1,2};
        // 预期87 实际89
        int n3 = 21;
        int k3 = 8;
        System.out.println(getMinCost(n3, k3, data3));*/

        /*
         [25,13,18,2,22,18,12,2,5,18,13,25,20,22,13,14,12,10,21,18]
        1 [25,13,18,2,22,18,12,2,5,18]   1*25  0   25
        2 [13,18,2,22,18,12,2,5,18,13]   2*13  1   26
        3 [18,2,22,18,12,2,5,18,13,25]   0*18  0
        4 [2,22,18,12,2,5,18,13,25,20]   10*2  9   20
        5 [22,18,12,2,5,18,13,25,20,22]  0*22  8
        6 [18,12,2,5,18,13,25,20,22,13]  0*18  7
        7 [12,2,5,18,13,25,20,22,13,14]  0*12  6
        8 [2,5,18,13,25,20,22,13,14,12]  4*2   9   8
        9 [5,18,13,25,20,22,13,14,12,10]   1*5 9   5
        10 [18,13,25,20,22,13,14,12,10,21] 0*18 8
        11 [13,25,20,22,13,14,12,10]   0*13 7
        12 [25,20,22,13,14,12,10,21]  0*25 6
        13 [20,22,13,14,12,10,21,18]  0*20 5
        14 [22,13,14,12,10,21,18]  0*22 4
        15 [13,14,12,10,21,18]  0*13 3
        16 [14,12,10,21,18]   0*14 2
        17 [12,10,21,18]   0*12 1
        18 [10,21,18]   2*10 2  20
        19 [21,18]  0*21 1
        20 [18]  0*18 0
        */

       /* int[] data4 = {25,13,18,2,22,18,12,2,5,18,13,25,20,22,13,14,12,10,21,18};
        // 预期104 实际89
        int n4 = 20;
        int k4 = 10;
        System.out.println(getMinCost(n4, k4, data4));*/

        // 预期：9 2*1+
        int[] data5 = {1,2,3,3,2};
        int n5 = 5;
        int k5 = 2;
        System.out.println(getMinCost(n5, k5, data5));
    }


    public static int getMinCost(int n, int k, int[] data) {
        return getMinCost(n, k, convertToList(data), 0, 1, 0);
    }

    public static int getMinCost(int n, int k, List<Integer> data, int boughtNum, int dayNum, int remainNum) {
        int thisCost = 0;
        if (dayNum > n) {
            return thisCost;
        }

        int canBuyNum = Math.min(k-remainNum, data.size()-remainNum);

        int min = data.stream().min(Integer::compareTo).get();
        int thisPriceItem = data.get(0);
        int thisBuyCount = 0;
        // 如果当天没食物
        if (thisPriceItem == min) {
            // 目前价格是范围内的最小值，则尽量多买
            thisBuyCount = canBuyNum;
        } else {
            // 如果不是最小，则找到比下一个它小的节点，尽量买到能支撑到这个节点的天数
            int nextSmallPriceIndex = 0;
            for (int i = 0; i < data.size(); i++) {
                if (data.get(i) < thisPriceItem) {
                    nextSmallPriceIndex = i;
                    break;
                }
            }
            if (remainNum < nextSmallPriceIndex) {
                thisBuyCount = Math.min(nextSmallPriceIndex - remainNum, canBuyNum);
            }
        }

        if (thisBuyCount > 0 ) {
            thisCost += thisPriceItem * thisBuyCount;
            boughtNum += thisBuyCount;
            remainNum += thisBuyCount;
        }
        remainNum--;

        System.out.println("dayNum: " + dayNum + "; boughtNum：" + boughtNum + "; remainNum：" + remainNum + ";thisBuyCount: " + thisBuyCount  + "; thisCost: " + thisCost);
        // 剩下的数据
        thisCost += getMinCost(n, k, data.subList(1, data.size()), boughtNum, dayNum+1, remainNum);
        return thisCost;
    }


    private static List<Integer> convertToList(int[] data) {
        List<Integer> list = new ArrayList<>();
        for (int i : data) {
            list.add(i);
        }
        return list;
    }

}
